package org.example.myleet.p430;

import org.example.myleet.Utils.Node;

public class Solution {
    /**
     * DFS
     */
    public Node flatten(Node head) {
        Node cur = head;
        while (cur != null) {
            if (cur.child != null) {
                //有孩子，扁平化之
                dfsFlatten(cur);
            }
            cur = cur.next;
        }
        return head;
    }

    private void dfsFlatten(Node parent) {
        Node head = parent.child;
        //记录当前节点
        Node cur = head;
        //记录上个节点，最后会变成链表的尾部
        Node prev = cur;
        while (cur != null) {
            if (cur.child != null) {
                //有孩子，扁平化之
                dfsFlatten(cur);
            }
            prev = cur;
            cur = cur.next;
        }
        //重置各相关节点的指针，parent和child建立互相指针，parent的next和链表的尾部建立互相指针
        Node next = parent.next;
        parent.next = head;
        head.prev = parent;
        prev.next = next;
        if (next != null) {
            next.prev = prev;
        }
        //最后将child指针置空
        parent.child = null;
    }
}
